This invention relates to a method for generating images by using a ray-tracing method.
First, overview is described for the ray-tracing method, for example, stated by Turner Whitted in "An Improved Illumination Model for Shaded Display", Com. of the ACM, June 1980, Vol. 23, No. 6. In the ray-tracing method, as shown in FIG. 2, ray L (line of sight) emitted from viewpoint 12 is supposed for each pel (i, j) on screen 10 (matched with a plane of projection for convenience of the description), and the surfaces of objects intersecting the ray are searched. Of objects 14 and 16 intersecting ray L, the first seen is object 14, whose surface is closer to the viewpoint.
Now, as shown in FIG. 3, it is assumed that, based on optical properties of an area of the outer surface of object 14 which ray L encounters, a reflected ray S.sub.1 and refracted ray T.sub.1 originates from intersection point 18. In this case, a search is made for each of ray S.sub.1 and T.sub.1 to determine whether it intersects any surface of any object or not. In the example of FIG. 3, ray S.sub.1 intersects object 20 at intersection point 22. If reflected ray S.sub.2 and refracted ray T.sub.2 originating from intersection point 22 exist, a search is made for each of them to determine whether it intersects an object surface or not. On the other hand, ray T.sub.1 intersects object 14 again at intersection point 24. If, owing to optical properties of an area of the internal surface of object 14 where intersection point 24 exists, a reflected ray originating from intersection point 24 cannot exist, or if the reflected ray is too weak for consideration, a search is made only for refracted ray T.sub.3 to determine whether it intersects an object surface or not. Thus, once an intersection point between a line of sight and a surface of an object to be displayed is found, tracing of a ray originating from the intersection point is sequentially performed. In FIG. 3, N.sub.1, N.sub.2 and N.sub.3 represent normal vectors at intersection points 18, 22 and 24, respectively.
Now, although the above-mentioned tracing of a ray may be almost infinitely repeated, it is usually discontinued appropriately, taking into consideration the time required for generating an image. For convenience of description, in the example of FIG. 2, a search is not performed for rays S.sub.2, T.sub.2 and T.sub.3 to determine whether there are intersection points between them and the surfaces of the object to be displayed.
Now, color, brightness, etc., of intersection point 18, of course, reflect attributes of the external surfaces of object 20 at intersection point 22 and those of the internal surfaces of object 14 at intersection point 24 as well as attributes of the external surfaces of object 14 at intersection point 18. Examples of attributes of an object are color specific thereto, its reflection coefficient, its unevenness, etc. Therefore, very real images can be generated by determining optical information such as color and brightness to be assigned to pel (i, j) on screen 10 (FIG. 2).
Methods for calculating intersection points of rays and each object surface are classified into an algebraic method and a method of numerical analysis on the basis of the figure of an object to be displayed.
The algebraic method is the one used to directly find an intersection point as the solution of an equation, according to a formula for solution.
The method of numerical analysis is one for searching a region where an intersection point exists first by sampling points on ray L as shown in FIG. 4. If an equation for an equi-valued surface is represented by F(X, Y, Z)=C, check is made for sign of [F(X, Y, Z)-C] on each sampled point to find a region where an intersection point exists, or a region where the sign changes (between sampled points 30 and 32 for the example of FIG. 4). Then, the intersection point is calculated for the region using the bisection method or the Newton method. In a case where the surface of the object to be displayed can be represented by a function of F(X, Y, Z)=C of the fifth degree or higher, the method of numerical analysis using the sampling becomes essential.
Although the ray-tracing method can generally generate a high quality image, the amount of calculation becomes enormous because an intersection point with the surfaces of the objects needs to be found for each pel, respectively. Therefore, the following method for increasing speed is disclosed by, for example, Akira Fujimoto et. al. in "Accelerated Ray-Tracing System", IEEE CG & A, April 1986 or Japanese PUPA 61-139890.
(I) Grid space 33 as shown in FIG. 5 is considered. Information about which object exists in rectangular parallelepiped (cell) 34 obtained by dividing grid space 33 is stored into storage means in the form of table 35.
(II) For each ray it is judged whether or not it intersects the grid space. Then for a ray intersecting the grid space, it is determined which rectangular parallelepiped the ray intersects, and finally whether or not it intersects the surface of the object contained in the rectangular parallelepiped.
Description is made by referring to the example shown in FIG. 6. Ray A intersects a rectangular parallelepiped where an object exists (for example, rectangular parallelepiped 38 where object 36 exists), but ray B does not intersect a rectangular parallelepiped where an object exists, and no calculation is required for the intersection point with an object surface. Because it is not necessary to calculate the intersection point with an object surface for a rectangular parallelepiped which contains no object, it is possible to reduce the number of calculations of the intersection point. 40 in FIG. 6 is a plane of projection.
Here, it is noticed that the invention and the prior art are described by using a drawing represented two-dimensionally for convenience of description as in FIGS. 3 through 6.
Whether a ray intersects a grid space or not is determined by finding intersection points with six planes forming the surfaces of the grid space which is in a form of a rectangular parallelepiped, and by checking whether the intersection points are contained in the grid space or not. If there is an intersection point contained in the grid space, a rectangular parallelepiped which the ray first enters is determined from the intersection point nearest to the viewpoint.
A rectangular parallelepiped which the ray next enters can be determined only by incremental calculation based on the first rectangular parallelepiped and inclination of the ray. Now, description is made by referring to FIG. 7. The equation for the ray is expressed by vt+s wherein inclination of ray is v, an intercept of the ray is s, and line parameter is t. In addition, it is assumed that the distance between X, Y and Z grids along the ray is dtx, dty and dtz, respectively, and that t parameter on X, Y and Z grid which the ray traverses next is tx, ty, tz, respectively. As shown in FIG. 7 that is represented two-dimensionally for convenience of the description, rectangular parallelepiped (i', j', k') which the ray enters next can be determined only by incrementing axis 1 (1=x, y, z), which has a minimum value among current tx, ty and tz, by 1 (+1 if the inclination is positive, -1 if it is negative). Once transfer to the next rectangular parallelepiped is made, dt1 (1=x, y, z) is added to t parameter t1 (1=x, y, z) for the axis. Then, rectangular parallelepipeds can be sequentially traversed by applying similar processing.
Now, in the case of the conventional method consisting of the above-mentioned (I) and (II), a rectangular parallelepiped completely included in an object to be displayed is registered and subject to sampling although an intersection point between the ray and the object surface cannot exist there. That is, as shown in FIG. 8, in a case where a ray passes through a transparent object having a plurality of rectangular parallelepipeds in grid space 42, sampling is performed for rectangular parallelepipeds 46 and 48 that do not require processing for searching the intersection point, which wastes time for that. This problem becomes serious particularly when it is necessary to generate images of a number of transparent objects.